package org.lql.algo.codecrush.week009.question.type.I;

import org.lql.algo.common.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: liangqinglong
 * @date: 2025-08-20 16:47
 * @description: 94. 二叉树的中序遍历 <a href="https://leetcode.cn/problems/binary-tree-inorder-traversal/description/">...</a>
 **/
public class InorderTraversal {

	/**
	 * * * 前序遍历：根-左-右
	 * * <p>
	 * * * 中序遍历：左-根-右
	 * * <p>
	 * * * 后序遍历：左-右-根
	 */
	public List<Integer> inorderTraversal(TreeNode root) {
		List<Integer> res = new ArrayList<>();
		if (root == null) {
			return res;
		}
		dfs(res, root);
		return res;
	}

	private void dfs(List<Integer> res, TreeNode root) {
		if (root == null) {
			return;
		}
		dfs(res, root.left);
		res.add(root.val);
		dfs(res, root.right);
	}

	public static void main(String[] args) {
		TreeNode root = new TreeNode(1);
		root.right = new TreeNode(2);
		root.right.left = new TreeNode(3);
		InorderTraversal inorderTraversal = new InorderTraversal();
		System.out.println(inorderTraversal.inorderTraversal(root));
	}
}
